<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Maximum Sum Rectangular Submatrix in Matrix</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="maximum-sum-rectangular-submatrix-in-matrix">Maximum Sum Rectangular Submatrix in Matrix</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=yCQN096CwWM&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=15">https://www.youtube.com/watch?v=yCQN096CwWM&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=15</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/SubRectangularMatrixWithMaximumSum.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/SubRectangularMatrixWithMaximumSum.java</a></li>
</ul>
<p><img src="file:///e:\gitee\leetcode\dp\pics\dp9.png" alt="dp9.png"></p>
<h2 id="我的python版本代码">我的python版本代码</h2>
<pre><code class="language-python"><div><span class="hljs-comment"># coding:utf-8</span>

<span class="hljs-keyword">from</span> pprint <span class="hljs-keyword">import</span> pprint

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxsum_rectangle</span><span class="hljs-params">(matrix)</span>:</span>
    <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> matrix <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> matrix[<span class="hljs-number">0</span>]:
        <span class="hljs-keyword">return</span>

    m = len(matrix)
    n = len(matrix[<span class="hljs-number">0</span>])
    ans = -float(<span class="hljs-string">'inf'</span>)
    ans_L = <span class="hljs-number">-1</span>
    ans_R = <span class="hljs-number">-1</span>
    <span class="hljs-keyword">for</span> L <span class="hljs-keyword">in</span> range(n):
        col = [<span class="hljs-number">0</span>] * m
        <span class="hljs-keyword">for</span> R <span class="hljs-keyword">in</span> range(L, n):
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(m):
                col[i] += matrix[i][R]
            maxsum = maxsum_array(col)
            <span class="hljs-keyword">if</span> maxsum &gt; ans:
                ans_L = L
                ans_R = R
                ans = maxsum
    print(<span class="hljs-string">f"ans=<span class="hljs-subst">{ans}</span> ans_L=<span class="hljs-subst">{ans_L}</span> ans_R=<span class="hljs-subst">{ans_R}</span>"</span>)


<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxsum_array</span><span class="hljs-params">(array)</span>:</span>
    ans = -float(<span class="hljs-string">'inf'</span>)
    cum = <span class="hljs-number">0</span>
    <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> array:
        cum += num
        ans = max(cum, ans)
        <span class="hljs-keyword">if</span> cum &lt; <span class="hljs-number">0</span>:
            cum = <span class="hljs-number">0</span>
    <span class="hljs-keyword">return</span> ans

<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">test1</span><span class="hljs-params">()</span>:</span>
    matrix = [
        [<span class="hljs-number">2</span>,<span class="hljs-number">1</span>, <span class="hljs-number">-3</span>,<span class="hljs-number">-4</span>,<span class="hljs-number">5</span>],
        [<span class="hljs-number">0</span>,<span class="hljs-number">6</span>,<span class="hljs-number">3</span>,<span class="hljs-number">4</span>,<span class="hljs-number">1</span>],
        [<span class="hljs-number">2</span>,<span class="hljs-number">-2</span>,<span class="hljs-number">-1</span>,<span class="hljs-number">4</span>,<span class="hljs-number">-5</span>],
        [<span class="hljs-number">-3</span>,<span class="hljs-number">3</span>,<span class="hljs-number">1</span>,<span class="hljs-number">0</span>,<span class="hljs-number">3</span>],
    ]
    pprint(matrix, width=<span class="hljs-number">60</span>)
    maxsum_rectangle(matrix)


<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">main</span><span class="hljs-params">()</span>:</span>
    test1()

<span class="hljs-keyword">if</span> __name__ == <span class="hljs-string">'__main__'</span>:
    main()
</div></code></pre>
<h1 id="2-一维的-kadane算法">2. 一维的 kadane算法</h1>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane's_algorithm">https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane's_algorithm</a></li>
<li><a href="https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%AD%90%E6%95%B0%E5%88%97%E9%97%AE%E9%A2%98/22828059?fr=aladdin">https://baike.baidu.com/item/最大子数列问题/22828059?fr=aladdin</a></li>
<li><a href="https://blog.csdn.net/dazhi2016/article/details/53617132">https://blog.csdn.net/dazhi2016/article/details/53617132</a></li>
</ul>
<p>Kadane算法的执行流程，从头到尾遍历目标数组，将数组分割为满足上述条件的子串，同时得到各子串的最大前缀和，然后比较各子串的最大前缀和，得到最终答案。我们以array={−2, 1, −3, 4, −1, 2, 1, −5, 4}为例，来简单说明一下算法步骤。通过遍历，可以将数组分割为如下3个子串（-2），（1，-3），（4，-1，2，1，-5，4），这里对于（-2）这样的情况，单独分为一组。各子串的最大前缀和为-2，1，6，所以目标串的最大子串和为6。（算法思想看不懂的话，就跟着程序走一遍，读完程序后就可以理解这个算法了）。</p>
<p>有一个关键的地方，如果数组中全为复数，怎么办？ 是否允许返回空的连续子数组？</p>
<h2 id="1-返回的子数组不能为空-那么答案就是最大的那个负数">(1) 返回的子数组不能为空， 那么答案就是最大的那个负数</h2>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">max_subarray</span><span class="hljs-params">(A)</span>:</span>
    max_ending_here = max_so_far = A[<span class="hljs-number">0</span>]
    <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> A[<span class="hljs-number">1</span>:]:
        max_ending_here = max(x, max_ending_here + x) 
        max_so_far = max(max_so_far, max_ending_here)
    <span class="hljs-keyword">return</span> max_so_far
</div></code></pre>
<h2 id="2-返回的子数组可以为空-那么答案就是0">(2) 返回的子数组可以为空， 那么答案就是0</h2>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">max_subarray</span><span class="hljs-params">(A)</span>:</span>
    max_ending_here = max_so_far = A[<span class="hljs-number">0</span>]
    <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> A[<span class="hljs-number">1</span>:]:
        max_ending_here = max(<span class="hljs-number">0</span>, max_ending_here + x) 
        max_so_far = max(max_so_far, max_ending_here)
    <span class="hljs-keyword">return</span> max_so_far
</div></code></pre>
<h1 id="3-lc-918-maximum-sum-circular-subarray-循环数组的max-subarray-sum问题">3. LC 918. Maximum Sum Circular Subarray 循环数组的max subarray sum问题</h1>
<ul>
<li><a href="https://leetcode.com/problems/maximum-sum-circular-subarray/">https://leetcode.com/problems/maximum-sum-circular-subarray/</a></li>
<li><a href="https://leetcode.com/problems/maximum-sum-circular-subarray/solution/">https://leetcode.com/problems/maximum-sum-circular-subarray/solution/</a></li>
</ul>
<h2 id="approach-1-next-array">Approach 1: Next Array</h2>
<p>基于动态规划， 不好懂，跳过。</p>
<h2 id="approach-2-prefix-sums--monoqueue">Approach 2: Prefix Sums + Monoqueue</h2>
<p>Let B = A+A be this fixed array.</p>
<p>Now say N=A.length, and consider the prefix sums</p>
<p>P_k = =B[0]+B[1]+⋯+B[k−1]</p>
<p>Then, we want the largest P_j - P_i  where j−i ≤ N.</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxSubarraySumCircular</span><span class="hljs-params">(self, A)</span>:</span>
        N = len(A)

        <span class="hljs-comment"># Compute P[j] = sum(B[:j]) for the fixed array B = A+A</span>
        P = [<span class="hljs-number">0</span>]
        <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> xrange(<span class="hljs-number">2</span>):
            <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> A:
                P.append(P[<span class="hljs-number">-1</span>] + x)

        <span class="hljs-comment"># Want largest P[j] - P[i] with 1 &lt;= j-i &lt;= N</span>
        <span class="hljs-comment"># For each j, want smallest P[i] with i &gt;= j-N</span>
        ans = A[<span class="hljs-number">0</span>]
        deque = collections.deque([<span class="hljs-number">0</span>]) <span class="hljs-comment"># i's, increasing by P[i]</span>
        <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> xrange(<span class="hljs-number">1</span>, len(P)):
            <span class="hljs-comment"># If the smallest i is too small, remove it.</span>
            <span class="hljs-keyword">if</span> deque[<span class="hljs-number">0</span>] &lt; j-N:
                deque.popleft()

            <span class="hljs-comment"># The optimal i is deque[0], for cand. answer P[j] - P[i].</span>
            ans = max(ans, P[j] - P[deque[<span class="hljs-number">0</span>]])

            <span class="hljs-comment"># Remove any i1's with P[i2] &lt;= P[i1].</span>
            <span class="hljs-keyword">while</span> deque <span class="hljs-keyword">and</span> P[j] &lt;= P[deque[<span class="hljs-number">-1</span>]]:
                deque.pop()

            deque.append(j)

        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<h2 id="approach-3-kadanes-sign-variant">Approach 3: Kadane's (Sign Variant)</h2>
<p>B = A+A 本题考虑两种情况</p>
<ol>
<li>所求最大sub array 都在第一个A内部</li>
<li>所求最大sub array 跨越了2个A</li>
</ol>
<p>本题的关键是如何求第二种情况。</p>
<p>Using Kadane's algorithm kadane for finding the maximum sum of non-empty subarrays, the answer for one-interval subarrays is kadane(A).</p>
<p>Now, let N = A.length. For a two-interval subarray like:</p>
<p>(A0 + A1 + .. Ai) + (Aj + A{j+1} + ... A{N-1})</p>
<p>we can write this as</p>
<p>sum(A) - (A{i+1} + A{i+2} + ... + A{j-1})</p>
<p>let B = A with each element multiplied by -1 , 所求就是</p>
<p>sum(A) + kadane(B)</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxSubarraySumCircular</span><span class="hljs-params">(self, A: List[int])</span> -&gt; int:</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">kadane</span><span class="hljs-params">(gen)</span>:</span>
            <span class="hljs-comment"># Maximum non-empty subarray sum</span>
            ans = -float(<span class="hljs-string">'inf'</span>)
            cur = <span class="hljs-number">0</span>
            <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> gen:
                cur = x + max(cur, <span class="hljs-number">0</span>)
                ans = max(ans, cur)
            <span class="hljs-keyword">return</span> ans

        S = sum(A)
        ans1 = kadane(iter(A))
        ans2 = S + kadane(-A[i] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, len(A)))  <span class="hljs-comment"># kadane(B[1:])</span>
        ans3 = S + kadane(-A[i] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(A) - <span class="hljs-number">1</span>)) <span class="hljs-comment"># kadane(B[:-1])</span>
        <span class="hljs-keyword">return</span> max(ans1, ans2, ans3)
    
</div></code></pre>
<p>这里有一个关键的细节，为什么不能写成下面这样</p>
<pre><code class="language-python"><div>        S = sum(A)
        ans1 = kadane(iter(A))
        <span class="hljs-comment">#ans2 = S + kadane(-A[i] for i in range(1, len(A)))</span>
        <span class="hljs-comment">#ans3 = S + kadane(-A[i] for i in range(len(A) - 1))</span>
        <span class="hljs-comment">#return max(ans1, ans2, ans3)</span>
        ans2 = S + kadane(-A[i] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">0</span>, len(A)))  <span class="hljs-comment"># kadane(B[:])</span>
        <span class="hljs-keyword">return</span> max(ans1, ans2)
</div></code></pre>
<p>如果数组A = [-2, -1, -3], 那么</p>
<pre><code>ans1 = kadane(A) = -1
ans2 = sum(A) + kadane(B) = -6 + 6 = 0
</code></pre>
<p>最后答案就是错误的ans2=0, 而不是正确的ans1=-1</p>
<p>所以我们用了下面的一个技巧来解决这个问题</p>
<p>We can remedy this problem by doing Kadane twice: once on B with the first element removed, and once on B with the last element removed.</p>
<pre><code class="language-python"><div>        ans1 = kadane(iter(A))
        ans2 = S + kadane(-A[i] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, len(A)))  <span class="hljs-comment"># kadane(B[1:])</span>
        ans3 = S + kadane(-A[i] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(A) - <span class="hljs-number">1</span>)) <span class="hljs-comment"># kadane(B[:-1])</span>
        <span class="hljs-keyword">return</span> max(ans1, ans2, ans3)
</div></code></pre>
<p>但其实有更简单的办法，针对所有元素都是负数的情况 A = [-2, -1, -3]， ans1 必然小于0， 我们加一个判断就行了, 下面是我的最终版本</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxSubarraySumCircular</span><span class="hljs-params">(self, A: List[int])</span> -&gt; int:</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">kadane</span><span class="hljs-params">(gen)</span>:</span>
            <span class="hljs-comment"># Maximum non-empty subarray sum</span>
            ans = -float(<span class="hljs-string">'inf'</span>)
            cur = <span class="hljs-number">0</span>
            <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> gen:
                cur = x + max(cur, <span class="hljs-number">0</span>)  <span class="hljs-comment"># 这里也可以写成 cur = max(cur+x, x)</span>
                ans = max(ans, cur)
            <span class="hljs-keyword">return</span> ans

        S = sum(A)
        ans1 = kadane(iter(A))
        <span class="hljs-keyword">if</span> ans1 &lt; <span class="hljs-number">0</span>:
            <span class="hljs-keyword">return</span> ans1
        <span class="hljs-comment">#ans2 = S + kadane(-A[i] for i in range(1, len(A)))</span>
        <span class="hljs-comment">#ans3 = S + kadane(-A[i] for i in range(len(A) - 1))</span>
        <span class="hljs-comment">#return max(ans1, ans2, ans3)</span>
        ans2 = S + kadane(-A[i] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">0</span>, len(A)))
        <span class="hljs-keyword">return</span> max(ans1, ans2)
</div></code></pre>
<h2 id="approach-4-kadanes-min-variant">Approach 4: Kadane's (Min Variant)</h2>
<p>和 Approach 3 思路一样， 就是实现有区别</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxSubarraySumCircular</span><span class="hljs-params">(self, A)</span>:</span>
        <span class="hljs-comment"># ans1: answer for one-interval subarray</span>
        ans1 = cur = <span class="hljs-literal">None</span>
        <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> A:
            cur = x + max(cur, <span class="hljs-number">0</span>)
            ans1 = max(ans1, cur)

        <span class="hljs-comment"># ans2: answer for two-interval subarray, interior in A[1:]</span>
        ans2 = cur = float(<span class="hljs-string">'inf'</span>)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> xrange(<span class="hljs-number">1</span>, len(A)):
            cur = A[i] + min(cur, <span class="hljs-number">0</span>)
            ans2 = min(ans2, cur)
        ans2 = sum(A) - ans2

        <span class="hljs-comment"># ans3: answer for two-interval subarray, interior in A[:-1]</span>
        ans3 = cur = float(<span class="hljs-string">'inf'</span>)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> xrange(len(A)<span class="hljs-number">-1</span>):
            cur = A[i] + min(cur, <span class="hljs-number">0</span>)
            ans3 = min(ans3, cur)
        ans3 = sum(A) - ans3
        
        <span class="hljs-keyword">return</span> max(ans1, ans2, ans3)
</div></code></pre>

    </body>
    </html>